//
// Created by Lenovo on 2024/2/28.
//
#include<bits/stdc++.h>
using namespace std;
//岛屿数量，深搜版
class Solution1 {
public:

    bool st[301][301];
    int m,n;            //m-行数，n-列数
    void dfs(int i,int j,vector<vector<char>>& grid){
        if(grid[i][j]=='0'){
            return;
        }
        //搜索上下左右是否能走
        if(i-1>=0 && i-1<m && !st[i-1][j] && grid[i-1][j]=='1'){
            st[i-1][j]= true;
            dfs(i-1,j,grid);
        }
        if(i+1>=0 && i+1<m && !st[i+1][j] && grid[i+1][j]=='1'){
            st[i+1][j]= true;
            dfs(i+1,j,grid);
        }
        if(j-1>=0 && j-1<n && !st[i][j-1] && grid[i][j-1]=='1'){
            st[i][j-1]= true;
            dfs(i,j-1,grid);
        }
        if(j+1>=0 && j+1<n && !st[i][j+1] && grid[i][j+1]=='1'){
            st[i][j+1]= true;
            dfs(i,j+1,grid);
        }
    }


    int numIslands(vector<vector<char>>& grid) {
        m=grid.size();
        n=grid[0].size();
        int cnt=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!st[i][j] && grid[i][j]=='1'){
                    cnt++;
                    st[i][j]= true;
                    dfs(i,j,grid);
                }
            }
        }
        return cnt;
    }
};

//岛屿数量，广搜版
class Solution2 {
public:

    bool st[301][301];
    int m,n;            //m-行数，n-列数

    void bfs(int i,int j,vector<vector<char>>& grid){
        queue<pair<int,int>> q;
        pair<int,int> p;
        p.first=i;
        p.second=j;
        st[i][j]=true;
        q.push(p);
        while(q.size()>0){
            pair<int,int> point=q.front();
            i=point.first;
            j=point.second;
            q.pop();
            if(i-1>=0 && !st[i-1][j] && grid[i-1][j]=='1'){
                st[i-1][j]=true;
                p.first=i-1;
                p.second=j;
                q.push(p);
            }
            if(i+1<m && !st[i+1][j] && grid[i+1][j]=='1'){
                st[i+1][j]=true;
                p.first=i+1;
                p.second=j;
                q.push(p);
            }
            if(j-1>=0 && !st[i][j-1] && grid[i][j-1]=='1'){
                st[i][j-1]=true;
                p.first=i;
                p.second=j-1;
                q.push(p);
            }
            if(j+1<n && !st[i][j+1] && grid[i][j+1]=='1'){
                st[i][j+1]=true;
                p.first=i;
                p.second=j+1;
                q.push(p);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        m=grid.size();
        n=grid[0].size();
        int cnt=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!st[i][j] && grid[i][j]=='1'){
                    cnt++;
                    bfs(i,j,grid);
                }
            }
        }
        return cnt;
    }
};
